/**
 * 猜数字游戏的规则如下：
 * 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
 * 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
 **/

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the guess number
 *			      1 if num is lower than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

#include<iostream>
using namespace std;

// 二分查找
class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right)
        {
            // 求每次二分后新区间的中点
            // 不直接相加除以2是为了避免溢出
            int mid = left + (right - left) / 2;
            if(guess(mid) <= 0){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left;     
    }
};
